package org.codingq92.hand;

/**
 * 自定义实现一个简单的HashMap
 *
 * @author: CodingQ92
 * @date: 2025/5/19 22:59
 */
public class CustomHashMap<K, V> {

    Node<K, V>[] table = new Node[16];

    private static int size = 0;

    public V put(K key, V value) {
        int index = getIndex(key);
        Node<K, V> head = table[index];
        // 1.当前下标的链表不存在该元素：全新的Node 直接写入链表
        if (null == head) {
            table[index] = new Node<>(key, value);
            size++;
            resize();
            return null;
        }
        // 2.当前下标的链表有相同key的Node
        while (true) {
            // 2.1 相同key的Node 直接替换并返回老的node value
            if (head.key.equals(key)) {
                V oldValue = head.value;
                head.value = value;
                return oldValue;
            }
            // 2.2 链表没有next了直接添加
            if (null == head.next) {
                head.next = new Node<>(key, value);
                size++;
                resize();
                return null;
            }
            head = head.next;
        }
    }

    public V get(K k) {
        int index = getIndex(k);
        Node<K, V> head = table[index];
        while (null != head) {
            if (head.key.equals(k)) {
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K k) {
        int index = getIndex(k);
        Node<K, V> head = table[index];
        // 元素不存在
        if (null == head) {
            return null;
        }
        // 当前下标链表头节点就是需要删除的节点 直接将头节点指向下一个节点
        if (head.key.equals(k)) {
            table[index] = head.next;
            size--;
            return head.value;
        }
        // 非头节点 遍历链表 找到需要删除的节点
        Node<K, V> pre = head;
        Node<K, V> current = head.next;
        while (null != current) {
            if (current.key.equals(k)) {
                pre.next = current.next;
                size--;
                return current.value;
            }
            pre = pre.next;
            current = current.next;
        }
        return null;
    }


    public int size() {
        return size;
    }

    private void resize() {
        if (size < table.length * 0.75) {
            return;
        }
        Node<K, V>[] newTable = new Node[table.length * 2];
        System.out.println("resize : " + table.length * 2);
        for (Node<K, V> head : table) {
            if (null == head) {
                continue;
            }
            Node<K, V> current = head;
            while (null != current) {
                int idx = head.key.hashCode() & (newTable.length - 1);
                if (null == newTable[idx]) {
                    newTable[idx] = current;
                    Node<K, V> next = current.next;
                    current.next = null;
                    current = next;
                } else {
                    Node<K, V> next = current.next;
                    current.next = newTable[idx];
                    newTable[idx] = current;
                    current = next;
                }
            }
        }
        table = newTable;
    }

    private int getIndex(K k) {
//        return k.hashCode() % table.length;
        return k.hashCode() & (table.length - 1);
    }

    class Node<K, V> {
        K key;
        V value;

        Node next;
        Node pre;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}
